package 中等.滑动窗口;

/**
 * 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组
 * nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要
 * 修改 数组以供接下来的操作使用。
 * 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero
 */
public class 将x减到0的最小操作数_1658 {

    public static void main(String[] args) {

        System.out.println(minOperations2(new int[]{1, 1}, 3));

    }

    /**
     * 转换思维
     * 等价于求 连续最长子数组 的和等于 sum - x
     * 题目要求 从头部连续取一些数 + 从尾部连续取一些数 = x ，且两部分总数最小
     * 那么中间部分越多，越满足题意
     *
     * @param nums
     * @param x
     * @return
     */
    public static int minOperations(int[] nums, int x) {
        int sum = 0, minOperate = nums.length + 1;
        for (int num : nums) {
            sum += num;
        }
        // curSum 表示 nums[left,right] 的和
        int left = 0, right = 0, curSum = 0;
        while (right < nums.length) {
            curSum += nums[right];

            // 如果当前和小于目标和，右边界一直扩张累加
            // 否则缩减左边界，直到小于目标和
            while (left <= right && curSum > sum - x) {
                curSum -= nums[left];
                left++;
            }

            if (curSum == sum - x) {
                minOperate = Math.min(minOperate, nums.length - (right - left + 1));
            }

            right++;
        }
        return minOperate <= nums.length ? minOperate : -1;
    }

    /**
     * 正向思维+前缀后缀和+双指针
     * 题目的要求可以看作前面选择几个数，后面选择几个数，和为 x
     * prefixSum[i] 代表 nums[0,i] 的和
     * suffixSum[i] 代表 nums[i,n-1] 的和
     * 指向前缀和的索引 left++ 代表前面选择的和变大，那么从后面选择的和需要变小
     * right++，使得 prefixSum[left] + suffixSum[right] <= x
     * 注意：
     * 有可能前面不选数字，全部从后面选择，也可以后面不选，全部冲前面选择
     */
    public static int minOperations2(int[] nums, int x) {
        int minOperate = Integer.MAX_VALUE;
        int n = nums.length;
        int[] prefixSum = new int[n];
        int[] suffixSum = new int[n];
        prefixSum[0] = nums[0];
        suffixSum[n - 1] = nums[n - 1];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
            suffixSum[n - 1 - i] = suffixSum[n - i] + nums[n - 1 - i];
        }
        for (int i = 0; i < n; i++) {
            if (prefixSum[i] == x) {
                minOperate = Math.min(minOperate, i + 1);
            }
            if (suffixSum[i] == x) {
                minOperate = Math.min(minOperate, n - i);
            }
        }
        int left = 0, right = 1;
        while (left < n) {
            while (right < n && prefixSum[left] + suffixSum[right] > x) {
                right++;
            }

            if (right < n && left < right && prefixSum[left] + suffixSum[right] == x) {
                minOperate = Math.min(minOperate, left + 1 + n - right);
            }
            left++;
        }
        return minOperate == Integer.MAX_VALUE ? -1 : minOperate;
    }

}
